package com.demo.java.OD151_200.OD196;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最多获得的短信条数】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145889293
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int budget = Integer.parseInt(sc.nextLine()); // 读取预算大小
        List<Integer> topup = Arrays.stream(sc.nextLine().split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList()); // 读取充值列表

        int[] dp = new int[budget + 1]; // 创建动态规划数组，用于记录不同预算下的最大充值金额
        for (int i = 1; i <= topup.size(); i++) { // 遍历充值列表
            for (int j = budget; j >= i; j--) { // 倒序遍历预算值
                // 当预算值大于等于当前充值金额时，计算选择当前充值金额和不选择当前充值金额的情况下的最大充值金额
                dp[j] = Math.max(dp[j], dp[j - i] + topup.get(i - 1));
            }
        }

        System.out.println(dp[budget]); // 输出预算下的最大充值金额
    }
}